복잡도 클래스

P는 다항 시간에 결정론적 튜링 기계로 해결할 수 있는 결정 문제들의 집합으로 정의된다. 여기서 다항 시간이란 알고리즘의 실행 시간이 입력 크기의 다항식 함수로 상한이 정해질 수 있음을 의미한다. 즉, 입력 크기를 n이라고 할 때, 실행 시간이 O(n^k) 형태로 표현되는 알고리즘으로 해결 가능한 문제들이 P 클래스에 속한다. 이 클래스는 일반적으로 '효율적으로 풀 수 있는' 문제들의 범주로 간주된다.

P 클래스의 대표적인 예시로는 두 수의 최대공약수를 구하는 유클리드 알고리즘, 정렬 문제, 최단 경로 문제 등이 있다. 이러한 문제들은 실용적인 시간 내에 해결책을 찾을 수 있어 컴퓨터 과학의 여러 응용 분야에서 널리 사용된다. P 클래스는 계산 복잡도 이론의 가장 기본적이고 중요한 복잡도 클래스 중 하나로, 다른 복잡도 클래스들을 이해하는 데 기준점이 된다.

P와 NP의 관계는 계산 이론의 가장 유명한 미해결 문제인 P-NP 문제의 핵심이다. P가 NP의 부분집합이라는 것은 명백하지만, 두 클래스가 실제로 동일한지(P=NP), 아니면 진부분집합 관계인지(P≠NP)는 아직 증명되지 않았다. 이 문제의 해답은 암호학, 알고리즘 설계, 인공지능을 비롯한 여러 분야에 지대한 영향을 미칠 것으로 예상된다.

NP는 비결정론적 다항 시간을 의미하는 복잡도 클래스이다. 이 클래스는 비결정론적 튜링 기계를 사용하여 다항 시간 내에 해를 검증할 수 있는 모든 결정 문제의 집합으로 정의된다. 즉, 어떤 문제의 해답이 주어졌을 때, 그 해답이 올바른지 다항 시간 내에 확인할 수 있다면 그 문제는 NP에 속한다고 말한다.

NP 클래스의 대표적인 예로는 충족 가능성 문제가 있다. 이 문제는 주어진 논리식을 참으로 만드는 변수 값의 조합이 존재하는지를 묻는다. 해답으로 제시된 변수 값의 조합을 논리식에 대입해보는 것은 다항 시간에 가능하므로, 이 문제는 NP에 속한다. 이 외에도 해밀턴 경로 문제, 외판원 문제 등 많은 조합 최적화 문제의 결정 문제 버전이 NP에 포함된다.

NP 클래스는 P 클래스와 밀접한 관계가 있다. P는 결정론적 튜링 기계로 다항 시간 내에 해를 *찾을* 수 있는 문제들의 클래스이다. 모든 P 문제는 자동으로 NP 문제이기도 하다. 왜냐하면 문제를 해결하는 알고리즘이 있다면, 그 알고리즘으로 생성된 해답을 검증하는 것은 더 쉽기 때문이다. 그러나 그 역, 즉 모든 NP 문제가 P인지 여부는 알려져 있지 않으며, 이것이 유명한 P-NP 문제의 핵심이다.

NP 클래스 내에는 특히 어려운 문제들이 모여 있는 NP-완전이라는 하위 집합이 존재한다. NP-완전 문제들은 NP 내의 모든 문제를 다항 시간 내에 환원할 수 있어, 만약 하나의 NP-완전 문제에 대한 다항 시간 알고리즘이 발견된다면, 모든 NP 문제가 P에 속하게 되어 P=NP가 증명된다.

NP-완전은 NP에 속하는 문제들 중 가장 어려운 문제들의 집합을 가리킨다. 정확히는, NP-완전 문제는 다음 두 가지 조건을 만족한다. 첫째, 그 문제 자체가 NP에 속해야 한다. 둘째, NP에 속하는 모든 다른 문제가 이 문제로 다항 시간 내에 환원될 수 있어야 한다. 이 환원 가능성은 만약 어떤 NP-완전 문제를 다항 시간에 해결할 수 있는 알고리즘이 발견된다면, 그 알고리즘을 이용해 NP에 속하는 모든 문제를 다항 시간에 풀 수 있음을 의미한다.

NP-완전 문제의 대표적인 예로는 충족 가능성 문제(SAT), 해밀턴 경로 문제, 외판원 문제 등이 있다. 이들은 실제 세계의 다양한 최적화 문제나 스케줄링 문제, 회로 설계 문제 등으로 변형되어 나타나며, 이론적으로나 실용적으로 매우 중요한 의미를 지닌다. 예를 들어, 암호학이나 운영 연구 분야에서 마주치는 많은 문제들은 NP-완전 문제의 일종으로 알려져 있다.

NP-완전 문제의 가장 큰 특징은 현재까지 이를 해결하는 효율적인, 즉 다항 시간 알고리즘이 알려져 있지 않다는 점이다. 그러나 그 문제가 어렵다는 증명 역시 이루어지지 않았다. 이는 P-NP 문제라는 컴퓨터 과학의 미해결 난제와 직결된다. 만약 P가 NP와 같다면, NP-완전 문제들도 다항 시간에 풀 수 있게 되지만, 그렇지 않다면 이 문제들은 본질적으로 어려운 문제로 남게 된다.

NP-완전성의 개념은 스티븐 쿡과 리처드 카프에 의해 정립되었다. 쿡은 1971년 충족 가능성 문제(SAT)가 NP-완전함을 증명했으며, 카프는 이후 21개의 다양한 조합론적 문제들이 NP-완전함을 보여주었다. 이들의 연구를 통해 수많은 문제들이 서로 연결되어 있으며, 그 중 하나라도 효율적으로 풀리면 모두 풀릴 수 있음이 밝혀졌다. 이는 문제의 난이도를 분류하고 이해하는 데 있어 결정적인 이정표가 되었다.

NP-난해(NP-hard)는 계산 복잡도 이론에서 정의되는 중요한 복잡도 클래스 중 하나이다. 이 클래스에 속하는 문제들은 NP에 속하는 모든 문제만큼이나 어렵거나 그보다 더 어려운 문제들로 구성된다. 구체적으로, 어떤 문제 H가 NP-난해라는 것은 NP에 속하는 모든 문제 L이 다항 시간 내에 H로 환원될 수 있음을 의미한다. 이 환원 과정을 통해 만약 NP-난해 문제 H를 다항 시간에 해결할 수 있는 알고리즘이 존재한다면, 그 알고리즘을 이용해 NP의 모든 문제도 다항 시간에 해결할 수 있게 된다.

NP-난해 클래스는 NP-완전 문제 클래스와 밀접한 관련이 있지만, 동일하지는 않다. 모든 NP-완전 문제는 NP-난해이면서 동시에 NP에 속한다. 반면, NP-난해 문제는 NP에 속하지 않을 수도 있다. 즉, NP-난해 문제 중에서 NP에 속하는 문제들이 바로 NP-완전 문제이다. 따라서 NP-난해 클래스는 NP-완전 클래스를 포함하는 더 넓은 범주의 어려운 문제들의 집합으로 볼 수 있다.

NP-난해 문제의 대표적인 예로는 정지 문제가 있다. 정지 문제는 튜링 기계가 주어진 입력에 대해 무한히 실행되는지 아닌지를 판단하는 문제로, 계산 가능성 이론에서 다루는 대표적인 판정 불가능 문제이다. 이 문제는 NP에 속하지 않지만, NP의 모든 문제를 다항 시간 내에 정지 문제로 환원할 수 있기 때문에 NP-난해로 분류된다. 이는 NP-난해 클래스가 NP보다 계산적으로 더 어려울 수 있는 문제들을 포함할 수 있음을 보여준다.

NP-난해 문제를 효율적으로 해결할 수 있는지, 즉 P에 속하는지는 P-NP 문제와 직결된 중요한 질문이다. 만약 단 하나의 NP-난해 문제라도 P에 속한다는 것이 증명된다면, 이는 모든 NP 문제가 P에 속함을 의미하며, 결국 P=NP가 성립하게 된다. 반대로, P≠NP라면 NP-난해 문제 중 그 어느 것도 다항 시간 알고리즘을 가질 수 없게 된다.

PSPACE는 계산 복잡도 이론에서 결정론적 튜링 기계나 비결정론적 튜링 기계가 다항식 공간을 사용하여 풀 수 있는 결정 문제들의 집합이다. 여기서 다항식 공간이란 문제의 입력 크기에 대한 다항식 함수로 표현되는 메모리 공간을 의미한다. 이는 문제를 해결하는 데 필요한 시간보다는 공간 자원에 초점을 맞춘 복잡도 클래스이다.

PSPACE에 속하는 대표적인 문제로는 양자화된 불린 공식 문제와 지리 게임이 있다. 또한 PSPACE-완전 문제는 PSPACE 클래스에서 가장 어려운 문제들로, 이들 중 하나를 다항식 시간에 해결할 수 있다면 PSPACE의 모든 문제를 다항식 시간에 해결할 수 있음을 의미한다. PSPACE-완전 문제의 예시로는 보편성을 확인하는 문제나 특정 게임 이론 문제들이 있다.

복잡도 클래스 간의 관계를 살펴보면, P ⊆ NP ⊆ PSPACE ⊆ EXP가 성립하는 것으로 알려져 있다. 이는 다항식 시간에 풀 수 있는 문제(P)는 비결정론적 다항 시간에 풀 수 있는 문제(NP)에 포함되며, 이는 다시 PSPACE에 포함되고, PSPACE는 지수 시간에 풀 수 있는 문제(EXP)에 포함된다는 것을 보여준다. 그러나 P와 PSPACE가 같은지, 혹은 NP와 PSPACE가 같은지는 아직 증명되지 않은 중요한 미해결 문제로 남아 있다.

EXP는 지수 시간(Exponential Time) 복잡도 클래스를 가리킨다. 이 클래스에 속하는 문제들은 결정론적 튜링 기계를 사용하여 지수 시간, 즉 입력 크기 n에 대해 O(2^p(n)) 시간(p(n)은 n의 다항식) 안에 풀 수 있는 결정 문제들로 구성된다. 다시 말해, 문제를 해결하는 데 필요한 최악의 경우 시간이 입력 크기에 대해 지수 함수적으로 증가하는 문제들의 집합이다.

EXP 클래스에는 매우 어려운 문제들이 포함된다. 예를 들어, 체스나 바둑과 같은 보드 게임의 완벽한 정보 하에서의 최적 수를 찾는 일반화된 문제, 특정한 종류의 푸시다운 오토마타에 대한 문제, 그리고 교대 튜링 기계를 사용한 일부 계산 문제 등이 EXP-완전한 문제로 알려져 있다. 이는 해당 문제들이 EXP 내에서 가장 어려운 문제들에 속함을 의미한다.

복잡도 클래스 간의 포함 관계에서 EXP는 PSPACE를 포함하는 것으로 알려져 있다. 모든 PSPACE 문제는 지수 시간 안에 풀 수 있기 때문이다. 또한, 시간 계층 정리에 의해 P ≠ EXP임이 증명되어 있다. 즉, 다항 시간에 풀 수 있는 모든 문제는 지수 시간에도 풀리지만, 그 역은 성립하지 않는다는 것이 밝혀져 있다.

EXP는 다항 시간 안에 풀 수 없는, 실용적으로는 매우 계산 비용이 큰 문제들을 이론적으로 분류하는 중요한 개념이다. 알고리즘 설계 시 문제가 EXP에 속한다는 것이 증명되면, 입력 크기가 조금만 커져도 현실적인 시간 내에 해를 구하는 것은 거의 불가능하므로, 근사 알고리즘이나 휴리스틱 방법을 모색해야 함을 시사한다.

계산 복잡도 이론에서 결정론적 튜링 기계는 가장 기본적이고 표준적인 계산 모델이다. 이 모델은 앨런 튜링이 제안한 튜링 기계에 기반하며, 주어진 입력에 대해 명확하게 정의된 규칙(전이 함수)에 따라 한 번에 하나의 동작만을 수행하는 기계를 의미한다. 즉, 특정 시점에서 기계의 다음 상태와 테이프에 쓸 내용, 헤드의 이동 방향은 현재 상태와 읽은 기호에 의해 유일하게 결정된다. 이러한 결정론적 특성은 현실의 컴퓨터가 동작하는 방식과 유사하다고 볼 수 있다.

결정론적 튜링 기계는 시간 복잡도와 공간 복잡도를 정의하는 데 기준이 된다. 예를 들어, 어떤 알고리즘이 다항 시간 내에 실행된다는 것은 그 알고리즘을 결정론적 튜링 기계로 구현했을 때, 입력 크기의 다항식 함수로 표현되는 시간 안에 정지한다는 것을 의미한다. 이렇게 정의된 복잡도 클래스 중 가장 유명한 것이 P 클래스이다. P는 결정론적 튜링 기계로 다항 시간 안에 해결할 수 있는 모든 판정 문제의 집합으로 정의된다.

이 모델의 중요성은 계산 가능성과 계산 복잡도의 이론적 토대를 제공한다는 점에 있다. 처치-튜링 논제는 모든 계산 가능한 함수는 결정론적 튜링 기계로 계산 가능하다고 주장하며, 이는 계산 이론의 근간이 된다. 또한, NP와 같은 다른 복잡도 클래스를 정의할 때도, 이를 검증하는 검증자는 결정론적 튜링 기계로 모델링된다. 따라서 결정론적 튜링 기계는 다양한 복잡도 클래스들을 서로 비교하고 그 관계를 연구하는 데 필수적인 도구이다.

비결정론적 튜링 기계는 계산 복잡도 이론에서 중요한 개념적 도구로, 계산 모델의 한 종류이다. 이 모델은 결정론적 튜링 기계와 달리, 주어진 시점에서 다음 상태로의 전이가 하나로 정해져 있지 않고 여러 가능성을 가질 수 있다. 즉, 기계는 '추측'을 할 수 있으며, 여러 계산 경로를 병렬적으로 탐색하는 것으로 비유할 수 있다. 이러한 비결정성은 계산 문제를 해결하는 데 필요한 시간 자원을 정의하는 데 핵심적인 역할을 한다.

NP라는 복잡도 클래스는 비결정론적 튜링 기계를 사용하여 다항 시간 내에 해를 검증할 수 있는 문제들의 집합으로 정의된다. 구체적으로, 어떤 문제의 답안(예: 해밀턴 경로 문제에서의 경로 후보)이 주어졌을 때, 비결정론적 튜링 기계는 이 답안이 올바른지 여부를 다항 시간 내에 확인할 수 있다면 그 문제는 NP에 속한다. 이는 문제를 '해결'하는 것보다 '검증'하는 것이 더 쉬울 수 있다는 직관을 형식화한 것이다.

비결정론적 튜링 기계는 현실적으로 구현 가능한 계산 모델은 아니지만, 이론적 분석을 위한 강력한 도구이다. 이를 통해 P와 NP의 관계, NP-완전 문제의 정의, 그리고 PSPACE나 EXP와 같은 더 높은 복잡도 클래스들을 체계적으로 연구할 수 있다. 특히, 모든 NP 문제를 다항 시간에 푸는 알고리즘이 존재하는지, 즉 P와 NP가 동일한지 여부는 P-NP 문제로 불리는 현대 수학과 컴퓨터 과학의 가장 유명한 미해결 문제 중 하나이다.

P-NP 문제는 계산 복잡도 이론에서 가장 유명하고 중요한 미해결 문제이다. 이 문제는 P 클래스와 NP 클래스가 사실상 동일한지, 즉 P = NP인지 P ≠ NP인지를 묻는다. 간단히 말해, 어떤 문제의 답을 쉽게 검증할 수 있다면(P에 속한다면), 그 문제의 답을 쉽게 찾을 수도 있는지(P에 속하는지)를 묻는 것이다.

만약 P = NP가 증명된다면, 이는 수학, 암호학, 인공지능, 운영연구 등 수많은 분야에 혁명적인 영향을 미칠 것이다. 예를 들어, 현재 공개키 암호의 안전성은 대부분 NP에 속하는 어려운 문제(예: 소인수분해, 이산 로그)를 기반으로 하는데, P = NP라면 이들 암호 체계는 효율적으로 깨질 수 있게 된다. 반대로, P ≠ NP가 증명된다면, 우리가 현재 직관적으로 느끼는 '어려운 문제'와 '쉬운 문제' 사이의 근본적인 차이가 존재함이 확인되는 것이며, 암호 체계의 이론적 기반이 공고해질 것이다.

이 문제는 클레이 수학연구소가 선정한 7개의 밀레니엄 문제 중 하나로, 해결자에게는 100만 달러의 상금이 수여된다. 수십 년간 수많은 학자들이 이 문제에 도전했으나, 아직 명확한 증명은 이루어지지 않았다. 대부분의 학자들은 P ≠ NP일 것이라고 추측하지만, 이를 엄밀하게 증명하거나 반증하는 것은 계산 이론의 근본을 뒤흔드는 매우 어려운 과제로 남아 있다.